# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# 前序遍历
class Solution:
    def isValidBST(self, root: Optional[TreeNode],left=-inf,right=inf) -> bool:
        if root is None:
            return True
        # 记录当前节点
        x = root.val
        # 要满足二叉搜索树，必须满足当前节点是 left < x < right 并且左边和右边都是符合二叉搜索树
        return left < x < right and self.isValidBST(root.left,left,x) and self.isValidBST(root.right,x,right)

# 中序遍历
class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        
        if not self.isValidBST(root.left):
            return False

        if root.val <= self.pre:
            return False

        self.pre = root.val
        return self.isValidBST(root.right) 

# 后序遍历
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def f(node):
            if node is None:
                return inf,-inf
            l_min,l_max = f(node.left)
            r_min,r_max = f(node.right)
            x = node.val
            if x<= l_max or x >= r_min:
                return -inf,inf
            return min(l_min,x),max(r_max,x)
        return f(root)[1] != inf
